1. Field of the Invention
This invention relates to an image processing apparatus and an image processing method.
2. Description of the Related Art
In the related art, an image transform apparatus which performs transform of an image in a virtual 3-dimensional space produces a model of a body shape composed of a combination of polygons such as triangles and performs texture mapping of affixing an image to the model to perform transform of the image. The image transform apparatus is disclosed, for example, in Japanese Patent Laid-Open No. 2002-83316.
Such an image transform apparatus as described above produces, for texture mapping, a texture address, which represents the position of each pixel of an image after transform to be outputted finally on an image to be affixed in texture mapping, in a unit of a polygon corresponding to the pixel. Then, the texture address is stored for each pixel into a memory. At this time, the image transform apparatus stores the texture address into an address of the memory corresponding to the position of a pixel corresponding to the texture address on a screen.
Examples of a mesh which is a set of polygons are described with reference to FIGS. 1A, 1B, 2A and 2B.
FIG. 1 shows a mesh 1 in the form of a square lattice. In particular, the mesh 1 is formed from squares 1C each formed from a polygon 1A and another polygon 1B and disposed in a lattice in a horizontal direction and a vertical direction perpendicular to the horizontal direction. The mesh 1 is used for modeling where transform in a fixed direction such as page turn or wave is involved. For example, if page turn is performed for the mesh 1 shown in FIG. 1A, then the mesh 1 exhibits such a form as seen in FIG. 1B.
FIG. 2A shows a concentric mesh 2. In particular, the mesh 2 is formed from quadrangles 2C each formed from a polygon 2A and another polygon 2B and disposed in radial directions and circumferential directions substantially perpendicular to the radial directions. The mesh 2 is used for modeling where concentric transform such as ripple is involved. For example, if ripple is performed for the mesh 2 shown in FIG. 2A, then the mesh 2 exhibits such a form as seen in FIG. 2B.
An image transform apparatus first produces a model after transform using such a mesh 1 or a mesh 2 as described above and then performs, based on data relating to apexes of polygons which form the model (such data are hereinafter referred to as apex data), apex operation such as modeling transform such as parallel movement, enlargement or reduction or rotation, clipping, perspective projection transform for projection on a screen and so forth in a unit of a polygon. Then, the image transform apparatus performs rasterization, a depth test, texture mapping or the like for converting apex data in a unit of a polygon obtained as a result of the apex operation into data relating to pixels (such data are hereinafter referred to as pixel data), and outputs a resulting image as an image after transform.
It is to be noted that each apex data includes, for example, data of a unit of an apex such as, for example, coordinate values of an apex on a modeling coordinate system, a texture address and a writing coefficient. Meanwhile, each pixel data includes z data representative of a z coordinate of a point at which a straight line interconnecting a virtual eye point and the pixel on the screen crosses the plane, the texture address, the writing coefficient and data representative of the position of the pixel on an output image (the data is hereinafter referred to as position data).
In order for the image transform apparatus to perform transform with a high degree of accuracy, it is necessary to use small size polygons. However, this gives rise to a problem that, for example, when a cache is used to store z data included in pixel data upon a depth test into a memory, the hit rate of the cache is deteriorated, resulting in increase in accessing to the memory.
This problem is described with reference to FIGS. 3 to 5.
It is to be noted that the following description given with reference to FIGS. 3 to 5 proceeds with an assumption that transform of an image is not performed. Also it is assumed that, in FIGS. 3 to 5, a cache used is configured such that z data of 4×4 pixels including four pixels juxtaposed in the horizontal direction and the vertical direction form a cache block which is a storage unit of the cache.
FIG. 3 shows a model 10 which uses a mesh in the form of a square lattice formed from polygons 111, 112, 113, 114, 115, . . . , 11n1, 11n1+1, . . . , 112n1, 112n1+1, . . . , 113n1, . . . . It is to be noted that, where there is no necessity to distinguish the polygons from one another, the polygons are collectively referred to as polygons 11.
It is to be noted that, in FIG. 3, each of round marks including white or void round marks and black or solid round marks represents a pixel, and the white and the black of the colors of the round marks represent a boundary between cache blocks. In particular, z data of pixels represented by white round marks and pixels represented by black round marks belong to cache blocks different from each other. Further, also z data of pixels of white round marks which do not neighbor with each other or z data of pixels of black round marks which do not neighbor with each other belong to cache blocks different from each other.
For example, referring to FIG. 3, z data of 16 pixels 151 to 154, 15m1+1 to 15m1+4, 152m1+1 to 152m1+4 and 153m1+1 to 153m1+4 represented by black round marks surrounded by a square 12, 16 pixels 155 to 158, 15m1+5 to 15m1+8, 152m1+5 to 152m1+8 and 153m1+5 to 153m1+8 represented by white round marks surrounded by a square 13, and z data of 16 pixels 159 to 1512, 15m1+9 to 15m1+12, 152m1+9 to 152m1+12 and 153m1+9 to 153m1+12 represented by black round marks surrounded by a square 14 belong to different cache blocks from one another. It is to be noted that, where there is no necessity to distinguish the pixels from one another, the pixels are hereinafter referred to collectively as pixels 15.
The image transform apparatus produces, for the polygons 11 which compose the model 10 of FIG. 3, apex data in an order in the horizontal direction in which the polygon 11 are disposed, that is, in an order in the direction indicated by an arrow mark A in FIG. 3.
In particular, the image transform apparatus first produces, for the n1 polygons 111 to 11n1 juxtaposed along the uppermost row in the vertical direction, apex data in a unit of a polygon 11 in the order of the polygons 111, 112, 113, 114, 115, . . . , 11n1, which is the order in which the polygons are juxtaposed in the horizontal direction. Then, the image transform apparatus produces, for the n1 polygons 11n1+1 to 112n1 juxtaposed along the second uppermost row in the vertical direction, apex data in a unit of a polygon 11 in the order of the polygons 11n1+1, . . . , 112n1, which is the order in which the polygons are juxtaposed in the horizontal direction. Thereafter, the image transform apparatus produces, for the n1 polygons 112n1+1, to 113n1 juxtaposed along the third uppermost row in the vertical direction, apex data in a unit of a polygon 11 in the order of the polygons 112n1+1, . . . , 113n1, which is the order in which the polygons are juxtaposed in the horizontal direction. Thereafter, apex data of the polygons 11 in the fourth uppermost and succeeding rows are successively produced similarly.
Further, the image transform apparatus performs apex operation for the apex data produced in such a manner as described above and performs rasterization for the apex data in the order in which the apex data are obtained to obtain pixel data.
In other words, the image transform apparatus obtains results of apex operation of apex data of the polygons 11 in the order of the polygons 111, 112, 113, 114, 115, . . . , 11n1, 11n1+1, . . . , 112n1, 112n1+1, . . . , 113n1, . . . and performs rasterization in the order. As a result, pixel data of the pixels 15 are obtained in the order of the pixels 151, 152, 153, 154, 155, . . . , 15m1, 15m1+1, . . . , 152m1, 152m1+1, . . . , 153m1, . . . corresponding to the polygons 111, 112, 113, 114, 115, . . . , 11n1, 11n1+1, . . . , 112n1, 112n1+1, . . . , 113n1, . . . , respectively.
Further, the image transform apparatus performs a depth test for the image data obtained as a result of the rasterization in the order in which the image data are obtained using the z data stored in the memory.
In particular, the image transform apparatus first reads out the z data of the pixels 151 to 154, 15m1+1 to 15m1+4, 152m1+1 to 152m1+4 and 153m1+1 to 153m1+4 surrounded by the square 12 as a cache block from the memory. Then, the image transform apparatus successively compares the z data of the pixels 151 to 154 and the z data included in the pixel data of the pixels 151 to 154 obtained as a result of the rasterization with each other in order, respectively, thereby to perform a depth test.
Then, the image transform apparatus first reads out the z data of the pixels 155 to 158, 15m1+5 to 15m1+8, 152m1+5 to 152m1+8 and 153m1+5 to 153m1+8 surrounded by the square 13 as a cache block from the memory. Then, the image transform apparatus successively compares the z data of the pixels 155 to 158 and the z data included in the pixel data of the pixels 155 to 158 obtained as a result of the rasterization with each other in order, respectively thereby to perform a depth test. Thereafter, the z data of the pixels 159 to 15m1 are compared with each other in a similar manner to perform a depth test.
At this time, since the number of cache blocks which can be stored into the cache is restricted, when a new cache block is to be read out, the image transform apparatus evicts the cache blocks in order beginning with the oldest cache block as occasion demands.
Accordingly, when the image transform apparatus is to perform a depth test for the pixel 15m1+1 after a depth text for pixel data of the pixels to 159 to 15m1, the z data of the 16 pixels 15 included in the square 12 which were read out as a cache block from the memory when the depth text for the pixels 151 to 154 was performed are usually evicted from the cache.
Therefore, when the depth test for the pixel 15m1+1 is to be performed, it is necessary for the image transform apparatus to read out the cache block of the 16 pixels 15 included in the square 12 again. In other words, it is necessary for the image transform apparatus to read out each cache block three times.
FIG. 4 shows a model 20 which uses a concentric mesh composed of polygons 21, and FIG. 5 shows another model 30 which uses a concentric mesh composed of polygons 31.
In FIG. 4, the image transform apparatus produces apex data and performs apex operation and rasterization of the polygons 21, which compose the model 20, in order in radial directions in which the polygons 21 are arranged thereby to obtain pixel data.
In particular, the image transform apparatus produces apex data and performs apex operation and rasterization of the polygons 21, which are juxtaposed in a radial direction B1, in order beginning with that polygon 21 which is positioned in the proximity of the center O of the model 20. Then, the image transform apparatus produces apex data and performs apex operation and rasterization of those polygons 21, which are positioned on the right side of the polygons 21 mentioned above, in order beginning with the polygon 21 positioned at the center O. Thereafter, apex data of the polygons 21 are produced and apex operation and rasterization are performed similarly.
As a result, it is necessary for the image transform apparatus to read out, for example, the z data of those pixels which are included in a square 22 as a cache block from the memory every time a depth test for pixel data corresponding to the polygons 21 juxtaposed in projection directions B1 and B2 and corresponding to the pixels. In other words, it is necessary to read out each cache block twice.
On the other hand, in FIG. 5, the image transform apparatus produces apex data and performs apex operation and rasterization of the polygons 31 which compose the model 30 of FIG. 5 in an order on concentric circles disposed on the polygons 31 thereby to obtain pixel data.
In particular, the image transform apparatus produces apex data and performs apex operation and rasterization of the polygons 31 juxtaposed concentrically in a circumferential direction C1 in an order of concentric circles on which the polygons 31 are disposed. Then, the image transform apparatus produces apex data and performs apex operation and rasterization of the polygons 31 which neighbor on the outer side of the polygons 31 and are juxtaposed concentrically in a arrow mark C2 in an order in which the polygons 31 are juxtaposed in the direction of the arrow mark C2. Thereafter, apex data of the polygons 31 are produced and apex operation and rasterization are performed similarly.
As a result, it is necessary for the image transform apparatus to read out, for example, the z data of the pixels included in a square 32 from the memory every time a depth test for the image data corresponding to the polygons 31 juxtaposed in the circumferential directions C1 to C4 corresponding to the pixels. In other words, it is necessary for the image transform apparatus to read out each cache block four times.